package 第二周;

/*
 * @author  YxinMiracle
 * @date  2022-04-25 18:17
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.Arrays;

public class 连续子数组的最大和 {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int[] sum = new int[nums.length+1];
        sum[0] = 0;
        int[] preMin = new int[nums.length+1];
        preMin[0] = sum[0];
        for (int i = 1; i <= nums.length; i++) sum[i] = sum[i-1] + nums[i-1];
        for (int i = 1; i <= nums.length; i++) preMin[i] = Integer.min(sum[i],preMin[i-1]);
        for (int i = 1; i <= nums.length; i++) {
            max = Integer.max(max,sum[i]-preMin[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(new 连续子数组的最大和().maxSubArray(nums));
    }

}
